<!DOCTYPE html>
<html>
	<head>
		<meta charset="utf-8" />
		<title></title>
	</head>
	<body>
		<script>
			//直接插入排序(折半)
			let arr = [0, 49, 38, 65, 97, 76, 13, 27, 49];

			function sort(arr, n) {
				let i, j, low, high, mid;
				for (i = 2; i <= n; i++) {
					// debugger
					arr[0] = arr[i];
					low = 1;high = i - 1;
					while (low <= high) {
						mid = Math.floor((low + high) / 2);
						if (arr[mid] > arr[0]) {
							high = mid - 1;
						} else {
							low = mid + 1;
						}
					}

					for (j = i - 1; j >= high + 1; j--) {
						arr[j + 1] = arr[j];
					}
					arr[high + 1] = arr[0];


				}
				return arr;
			}
			console.log(sort(arr, arr.length));
		</script>
	</body>
</html>
